package com.lijing.ThreadedBinaryTree;

/**
 * @Description 中序遍历线索二叉树
 * @title: InfixOrderThreadedBinaryTree
 * @Author LiJing
 * @Date: 2021/2/189:57 下午
 * @Version 1.0
 */
public class InfixOrderThreadedBinaryTree {
    private HeroNode root;
    private HeroNode pre;

    public HeroNode getRoot() {
        return root;
    }

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public HeroNode getPre() {
        return pre;
    }

    public void setPre(HeroNode pre) {
        this.pre = pre;
    }

    public InfixOrderThreadedBinaryTree() {
    }

    public InfixOrderThreadedBinaryTree(HeroNode root) {
        this.root = root;
    }

    /**
     * 重载方法
     */
    public void infixThreadedNodes(){
        this.infixThreadedNodes(root);
    }
    /**
     * 中序遍历线索化
     * @param node 被线索化的节点
     */
    public void infixThreadedNodes(HeroNode node){
        if (node == null){
            return;
        }
        /*
         * @Date: 2021/2/19 9:07 上午
         * Step 1: 线索化左子树
         */
        infixThreadedNodes(node.getLeft());
        /*
         * @Date: 2021/2/19 9:08 上午
         * Step 2: 线索化当前节点
         */
        if (node.getLeft() == null){
            //让当前节点的左指针指向前驱节点，并修改当前节点的左指针类型
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //处理后继节点
        if (pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        /*
         * @Date: 2021/2/19 9:08 上午
         * Step 3: 线索化右子树
         */
        infixThreadedNodes(node.getRight());
    }

    /**
     * 中序遍历(非递归)
     */
    public void infixThreadedList(){
        HeroNode node = root;
        if (root == null){
            System.out.println("二叉树为空，无法遍历！");
            return;
        }
        while (node != null){
            /*
             * @Date: 2021/2/19 9:28 上午
             * Step 1: 先找到最左边的元素
             */
            while(node.getLeftType() == 0){
                node = node.getLeft();
            }
            /*
             * @Date: 2021/2/19 9:30 上午
             * Step 2: 打印当前节点
             */
            System.out.println(node);
            /*
             * @Date: 2021/2/19 9:30 上午
             * Step 3: 对线索化的节点单独处理
             */
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            /*
             * @Date: 2021/2/19 9:34 上午
             * Step 4:该节点没有线索化后继节点，遍历到下一个右子节点
             */
            node = node.getRight();
        }
    }

    /**
     * 递归中序遍历
     * @param node 待遍历的首节点
     */
    public void infixOrderThreadedList(HeroNode node){
        /*
         * @Date: 2021/2/19 4:52 下午
         * Step 1: 打印左子树
         */
        if (node.getLeft() != null && node.getLeftType() == 0){
            infixOrderThreadedList(node.getLeft());
        }
        /*
         * @Date: 2021/2/19 4:52 下午
         * Step 2: 打印当前节点
         */
        System.out.println(node);
        /*
         * @Date: 2021/2/19 4:54 下午
         * Step 3: 打印右子树
         */
        if (node.getRight() != null && node.getRightType() == 0){
            infixOrderThreadedList(node.getRight());
        }
    }
}
